package cn.z2huo.algorithm.binarytree;

import java.util.LinkedList;
import java.util.Queue;

// 判断一棵树是否是对称的
public class SymmetricTree {
    public boolean isSymmetric(TreeNode node){
        if (node==null) return true;
        // 从根结点开始判断，判断根结点的左右孩子是否是镜像
        return isMirror(node.getLeft(), node.getRight());
    }

    // 递归的方式判断两个节点是否是镜像关系
    public boolean isMirror(TreeNode node, TreeNode node2){
        // 如果两个节点都不为空
        if (node!=null && node2!=null){
            // 判断两个节点的值是否相等，如果相等则继续向下判断是否为镜像；如果不想等则返回false
            if (node.getValue()==node2.getValue()){
                // 两个堂兄弟（同辈但父亲不同，父亲是兄弟）节点，其中的一个节点的左孩子是另一个节点的右孩子的镜像，右孩子是另一个节点的左孩子的镜像
                return isMirror(node.getRight(), node2.getLeft()) && isMirror(node.getLeft(), node2.getRight());
            }else {
                return false;
            }
        // 如果两个节点都为空，则存在镜像关系
        }else if (node==null && node2==null){
            return true;
        // 如果两个节点其中一个为空，则非镜像关系
        }else {
            return false;
        }
    }

    // 迭代的方式判断是否是镜像关系
    public boolean isMirror(TreeNode root){
        if (root==null) return true;
        Queue queue = new LinkedList();
        queue.offer(root.getLeft());
        queue.offer(root.getRight());
        while (!queue.isEmpty()){
            TreeNode node = (TreeNode) queue.poll();
            TreeNode node2 = (TreeNode) queue.poll();
            if (node!=null && node2!=null){
                if (node.getValue()==node2.getValue()){
                    queue.offer(node.getRight());
                    queue.offer(node2.getLeft());
                    queue.offer(node.getLeft());
                    queue.offer(node2.getRight());
                }else {
                    return false;
                }
            }else if (node==null && node2==null){
                continue;
            }else {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args){
        int[] array = {1,2,2,3,4,4,3};
//        int[] array = {1,2,2,0,3,0,3};
//        int[] array = {};
        BinaryTree bt = new BinaryTree();
        TreeNode root = bt.createTree(array);

        SymmetricTree symmetricTree = new SymmetricTree();
        System.out.println(symmetricTree.isSymmetric(root));
        System.out.println(symmetricTree.isMirror(root));
    }
}